package 并查集;

/**
 * @Question no5
 * @Date 2023/3/2 8:28
 * @Solution
 */
public class no5 {
    public static void solve(char[][] board) {
        //遍历边界，遇到边界O则开始dfs，并把边界O和与边界O联通的O变为#
        int row=board.length;
        int col=board[0].length;
        for(int i=0;i<col;i++) {
            //上边界
            if(board[0][i]=='O' || board[0][i]=='A') {
                board[0][i]='#';
                dfs(board,0,i);
            }
            //下边界
            if (board[row - 1][i] == 'O' || board[row-1][i]=='A') {
                board[row-1][i]='#';
                dfs(board,row-1,i);
            }
        }
        for(int i=0;i<row;i++) {
            //左边界
            if (board[i][0] == 'O' || board[i][0]=='A') {
                board[i][0]='#';
                dfs(board, i, 0);
            }
            //右边界
            if(board[i][col-1]=='O' || board[i][col-1]=='A') {
                board[i][col-1]='#';
                dfs(board,i,col-1);
            }
        }
        //第二次遍历，遇到O就修改为X，遇到#就修改为O
        for(int i=0;i<row;i++) {
            for(int j=0;j<col;j++) {
                if(board[i][j]=='#' || board[i][j]=='A') {
                    board[i][j]='O';
                } else if(board[i][j]=='O'||board[i][j]=='B') {
                    board[i][j]='X';
                }
            }
        }
    }
    public static void dfs(char[][] board,int x,int y) {
        //#代表为边界O，A代表为遍历过的与边界联通的，B代表遍历过的与边界不联通的
        //上边
        if(x-1!=-1 && board[x-1][y] != 'A' && board[x-1][y] != '#' && board[x-1][y] != 'B') {
            if(board[x-1][y]=='O') {
                if (board[x - 1][y] != '#') {
                    board[x - 1][y] = 'A';
                }
                dfs(board,x-1,y);
            } else {
                board[x-1][y]='B';
            }
        }
        //下边
        if(x+1!=board.length && board[x+1][y] != 'A' && board[x+1][y] != '#' && board[x+1][y] != 'B') {
            if(board[x+1][y]=='O') {
                if (board[x + 1][y] != '#') {
                    board[x + 1][y] = 'A';
                }
                dfs(board,x+1,y);
            } else {
                board[x + 1][y] = 'B';
            }
        }
        //左边
        if(y-1!=-1 && board[x][y-1] != 'A' && board[x][y-1] != '#' && board[x][y-1] != 'B') {
            if( board[x][y-1]=='O') {
                if (board[x][y - 1] != '#') {
                    board[x][y - 1] = 'A';
                }
                dfs(board, x, y - 1);
            } else {
                board[x][y-1]='B';
            }
        }
        //右边
        if(y+1!=board[0].length && board[x][y+1] != 'A' && board[x][y+1] != '#' && board[x][y+1] != 'B') {
            if(board[x][y+1]=='O') {
                if (board[x][y + 1] != '#') {
                    board[x][y + 1] = 'A';
                }
                dfs(board, x, y + 1);
            } else {
                board[x][y+1]='B';
            }
        }
    }

    public static void main(String[] args) {
        solve(new char[][]{{'O','O','O'},{'O','O','O'},{'O','O','O'}});
    }
}
